package _18_剑指OfferII;

public class _062_剑指OfferII实现前缀树 {

    // 哨兵
    Node first;

    /**
     * Initialize your data structure here.
     */
    public _062_剑指OfferII实现前缀树() {
        first = new Node();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        int len = word.length();
        Node node = first;
        for (int i = 0; i < len; ++i) {
            char cur = word.charAt(i);
            Node child = node.getChildren()[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            Node newNode = new Node();
            // 未找到匹配元素
            node.getChildren()[cur - 'a'] = newNode;
            node = newNode;
        }
        // 添加单词标记
        node.isWord = true;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        Node node = getNode(word);
        return node != null && node.isWord;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    private Node getNode(String word) {
        Node node = first;
        int len = word.length();
        for (int i = 0; i < len; ++i) {
            char cur = word.charAt(i);
            Node child = node.getChildren()[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            return null;
        }
        return node;
    }

    static class Node {

        boolean isWord;

        Node[] children;

        public Node[] getChildren() {
            if (children == null) {
                children = new Node[26];
            }
            return children;
        }
    }

}
